%\section{Proof for WeightedInternalCover in NP}

WEIGHTEDINTERVALCOVER is in NP.
	\begin{enumerate}
	\item[1.] Algorithm description
		\begin{enumerate}
			\item[1)] Let the string $R=a_1,b_1,c_1,a_2,b_2,c_2, \cdots, a_m,b_m,c_m,$  consists of random numbers appearing in repeated pattern of two reals followed by a natural number.
			\item[2)] If there are fewer than $3\cdot K$ numbers in $R$ the answer is NO. If $1\leq a_i < b_i \leq (n+1)$ where $i=i,\cdots,m$ does not hold the answer is again NO. Otherwise, consider the first $3\cdot K$ numbers from $R$ and inspect if the following holds 
\begin{displaymath}
	\sum_{\{j|i+\frac{1}{2}\in [a_j,a_j] \}} c_j = y_i
\end{displaymath}
for all $y_i$, $i=1,\cdots,n$. if it does the answer is YES, otherwise the answer is NO.
		\end{enumerate}
	\item[3.] Running time of the algorithm. There are $K$ interval-number pairs and $n$ $y$-s in total. First, the algorithm checks if there are fewer than $3\cdot K$ numbers in $R$ - an operation with running time bounded by $O(3K)$. Second, it is checked if each two reals in the first $K$ triples form a valid interval. This operation can be performed in $O(3K)$. Finally, the algorithm inspects if all $y_i$, $i=1,\cdots,n$ are covered by the set of weighted intervals. The running time of this operation is bounded by $O(nK)$. Consequently, the total running time of the algorithm is $O(nK)$. Therefore the algorithm is $p$-bounded where $p(n,m)=c \cdot n\cdot m$ for some constant $c$.

\item[2.] Verification of the conditions of Definition 3.14 (from the course script). First, we assume that the true answer is YES; there is a set $I=\{<[a_1,b_1],c_1>,\cdots,[a_K,b_K],c_K\}$ of at most $K$ pairs of intervals $[a_i,b_i]$, $1\leq a_i < b_i \leq (n+1)$, and natural numbers $c_i$, such that for all $i \in\{1,\cdots,n\}$
\begin{displaymath}
	\sum_{\{j|i+\frac{1}{2}\in [a_j,a_j] \}} c_j = y_i
\end{displaymath}
Let us now consider the string $R=a_1,b_1,c_1, \cdots ,a_K,b_K,c_K$ . Clearly, the algorithm would return YES if $R$ is given as the input string as $R$ is suffciently long and encodes a set of weighted intervals that covers the sequence of $y$-s. Hence, $P_R[A(X,R)=YES]>0$. Now, lets assume that the true answer is NO i.e. no set of weighted intervals with the desired properties can be found. The algorithm described above would always return NO in this case. Why? We establish this result by contradiction. If the aswer returned by the algorithm is YES then there is a string $R$  sufficiently long whose first $3\cdot K$ numbers encode a set of weighted intervals that covers the sequence of $y$-s. But, this contradicts our assumption that the true answer is NO. This concudes the prove.
	\end{enumerate}